public class Main {
    /*
     * 合并两个有序链表
     * 类似与合并两个有序数组
     * */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode pre1 = l1;
        ListNode cur2 = l2;
        ListNode pre2 = l2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                while (cur1 != null && cur1.val < cur2.val) {
                    pre1 = cur1;
                    cur1 = cur1.next;
                }
                pre1.next = cur2;
            } else {
                while (cur2 != null && cur2.val <= cur1.val) {
                    pre2 = cur2;
                    cur2 = cur2.next;
                }
                pre2.next = cur1;
            }
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        return l1.val >= l2.val ? l2 : l1;
    }
}